package com.muchfish.algorithm.stack;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/min-stack/description/">题目：155. 最小栈</a>
 * <br>
 * 题目描述：<br>
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。<br>
 * 实现 MinStack 类:<br>
 * MinStack() 初始化堆栈对象。<br>
 * void push(int val) 将元素val推入堆栈。<br>
 * void pop() 删除堆栈顶部的元素。<br>
 * int top() 获取堆栈顶部的元素。<br>
 * int getMin() 获取堆栈中的最小元素。<br>
 * <br>
 * 解题思路： <br>
 * <img src="https://assets.leetcode-cn.com/solution-static/155/155_fig1.gif"><br>
 * 方法：每次入栈的时候，比较当前元素和上一个元素，如果当前元素小于上一个元素，则将当前元素作为最小元素入栈，否则将上一个元素入栈。
 * <br>
 */
public class Stack2 {
    public static void main(String[] args) {

    }
}
class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
        return xStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}